1. Field of the Invention
The present invention relates in general to an improved data processing system and in particular to an improved system and method for increasing the efficiency of execution of a processor in restoring a state of the processor. Still more particularly, the present invention relates to an improved system and method for restoring a pipelined processor to the proper state after a branch which is mispredicted where the restoration does not degrade the performance of the processor and where instructions within the improved data processing system are tracked in groups.
2. Description of the Related Art
High performance processors currently utilized in data processing systems today may be capable of “superscalar” operation and may have “pipelined elements.” A superscalar processor has multiple elements which operate in parallel to process multiple instructions in a single processing cycle. Pipelining involves processing instructions in stages, so that the pipelined stages may process a number of instructions concurrently. In these high performance microprocessors, it is also advantageous to support speculative execution of instructions using branch prediction mechanisms, out-of order execution, and multiple pipelines in order to increase the number of instructions being processed at one time.
While instructions may be originally prepared to be processed in some logical programmed sequence, it should be understood that the instructions may be processed, in some respects, in a different sequence through speculative execution. However, since instructions are not totally independent of one another, complications may arise. Furthermore, if one instruction is dependent on a first instruction and the instructions are to be processed concurrently or the dependent instruction is to be processed before the first instruction, an assumption must be made regarding the result produced by the first instruction.
If an assumption used for processing an instruction proves to be incorrect then the result produced by the processing of the instruction will almost certainly be incorrect. Therefore, the pipeline must be flushed of all instructions after the instruction for which the assumption is made and the processor state must recover to a state with known correct results up to the instruction for which the assumption is made. (Herein, an instruction for which an assumption has been made is referred to as an “interruptible instruction,” and the determination that an assumption is incorrect, triggering the need for the processor state to recover to a prior state, is referred to as an “interruption” or an “interrupt point.”) For example, when a branch instruction is speculatively executed, but is mispredicted, an interruption occurs and the processor needs to return to the state of the branch instruction and abandon any instructions or results executed thereafter. Moreover, in addition to the previous example, there are other events which may occur which require recovery of the processor state due to an interrupt.
A completion table or re-order buffer is known for saving a processor state before an interruptible instruction so that if an interrupt does occur, the completion table control logic may recover the processor state to the interrupt point. In a shallow-pipelined processor, saving the state of each interruptible instruction within the pipeline is relatively easy and many such methods have been developed. However, in a deep-pipelined processor, the number of available pipeline stages is increased, whereby the number of possible active instructions is increased. Saving the state of each interruptible instruction in the same manner as for shallow-pipelines would require a much larger set of state information with greater complexity for restoration. In addition, in microprocessors which allow multiple branch predictions at one time, the complexity of storing the state information needed to restore the processor state increases dramatically as the number of positions in a pipeline increases.
In keeping a record in the completion table for each instruction, a large number of records are created without ever being utilized and the space utilized to store the groups of records is inefficient. For example, in order to keep track of N active instructions with a maximum of M instructions dispatched per cycle, it would be necessary to create M records to be saved during the dispatch cycle. Furthermore, N state records must be kept so that the state of the processor can be restored when an interrupt occurs. When M and N grow in wide dispatch and deep-pipelined processors, the complexity to create, manage and retrieve records has a negative impact on the high frequency ability of the microprocessor.
There is a need for a method of bookkeeping for a deep-pipelined processor such that the number of records and complexity thereof is reduced. In addition, for such a method, it is desirable that a deep-pipeline processor may be utilized without the performance of the microprocessor being degraded due to branch and other interruptible instructions in speculative execution. Furthermore, for such a method, it is desirable that in particular, in the event of a branch misprediction or other such interruptible instructions for which a fast restoration time is desired, the pipeline is quickly flushed and the processor restored to the proper state before the branch misprediction occurred.